# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    """
    分别递归查找左子树和右子树。
    """
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> TreeNode or None:
        if root is None:
            return
        # 刚好找到p或者q，则直接返回当前节点
        if root.val == p.val or root.val == q.val:
            return root
        # 递归查找左子树和右子树(代码模板，无脑记住)
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # 左子树和右子树都不为空，则p和q在节点的左右子树，root为最近公共祖先
        if left and right:
            return root
        # 若左子树不为空，则left为最近公共祖先节点，指向p或q或p、q均在左子树
        if left:
            return left
        # 若右子树不为空，则right为最近公共祖先节点，指向p或q或p、q均在右子树中
        if right:
            return right
